package someTestExcemple.huaweiOd.container.mapAndList;
import java.util.*;
//华为OD机试 - 查找充电设备组合 - 子集和问题（Java 2024 E卷 100分）
//https://blog.csdn.net/guorui_java/article/details/130610867
//这道题目涉及一个典型的“子集和问题”，
//我们需要在给定的充电设备功率的所有组合中，找到一个组合的总功率最接近但不超过最大输出功率p_max。

//todo 子集合问题
public class LookingChargingDevices {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 读取充电设备的个数n
        int n = sc.nextInt();

        // 初始化一个List存储每个充电设备的输出功率
        List<Integer> devices = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            devices.add(sc.nextInt());
        }

        // 读取充电站的最大输出功率p_max
        int p_max = sc.nextInt();

        // 初始化max为0，用于存储当前找到的最接近p_max的功率组合
        int max = 0;

        // 初始化一个Set用于存储所有可能的功率组合的和
        Set<Integer> matchSet = new HashSet<>();
        matchSet.add(0);  // 初始时只有一个元素0，表示不选择任何设备时功率为0

        // 遍历每个充电设备的输出功率
        for (Integer device : devices) {
            // 新的集合，用于存储在当前设备的基础上可以形成的新的功率组合
            Set<Integer> objects1 = new HashSet<>();

            // 遍历现有的所有功率组合
            for (Integer object : matchSet) {
                // 尝试将新设备加入-形成新的功率组合
                int newobj = object + device;

                // 只考虑不超过p_max的功率组合
                if (newobj <= p_max) {
                    objects1.add(newobj);  // 加入新的功率组合
                    max = Math.max(max, newobj);  // 更新max，记录最优功率
                }
            }
            //// 将新形成的所有功率组合加入到主集合中
            if(!objects1.isEmpty()) {
                matchSet.addAll(objects1);

            }
        }

        // 输出最接近p_max的功率组合值
        System.out.println(max);
    }
}
/**
 * 1、输入
 * 5
 * 20 30 40 50 60
 * 90
 *
 * 2、输出
 * 90
 */
/**
 * 5
 * 10 60 20 30 40
 * 36
 */
